package main

import "fmt"

func main() {
	n1 := &TreeNode{Val: 1}
	n2 := &TreeNode{Val: 2}
	n3 := &TreeNode{Val: 3}
	n4 := &TreeNode{Val: 4}
	n1.Left = n2
	n1.Right = n3
	n2.Left = n4

	n5 := &TreeNode{Val: 2}
	n6 := &TreeNode{Val: 4}
	n5.Left = n6

	n7 := &TreeNode{Val: 3}

	res := isSubStructure(n1, n5)
	fmt.Println(res)

	res2 := isSubStructure(n1, n7)
	fmt.Println(res2)

}

var ans bool

func isSubStructure(A *TreeNode, B *TreeNode) bool {
	ans = false
	dfs(A, B)
	return ans
}

func dfs(rootA *TreeNode, rootB *TreeNode) {
	if rootA == nil {
		return
	}
	if ans {
		return
	}
	if rootA.Val == rootB.Val {
		ans = helper(rootA, rootB)
	}
	dfs(rootA.Left, rootB)
	dfs(rootA.Right, rootB)
}

func helper(rootA *TreeNode, rootB *TreeNode) bool {
	if rootB == nil {
		return true
	}
	if rootA == nil && rootB != nil {
		return false
	}
	if rootA.Val != rootB.Val {
		return false
	}
	return helper(rootA.Left, rootB.Left) && helper(rootA.Right, rootB.Right)
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}
